class solution1:
    def largestRectangleArea(self, heights: list[int]) -> int:
        length = len(heights)
        if length == 0:
            return 0
        if length == 1:
            return heights[0]
        area = 0
        stack = list()
        for i in range(length):
            while len(stack) != 0 and heights[stack[-1]] > heights[i]:
                height = heights[stack.pop()]
                while len(stack) != 0 and heights[stack[-1]] == height:
                    stack.pop()
                if len(stack) == 0:
                    width = i
                else:
                    width = i - stack[-1] - 1
                area = max(area, width * height)
            stack.append(i)
        while len(stack) != 0:
            height = heights[stack.pop()]
            while len(stack) != 0 and heights[stack[-1]] == heights[i]:
                stack.pop()
            if len(stack) == 0:
                width = length
            else:
                width = length - stack[-1] - 1
            area = max(area, width * height)
        return area


class solution2:
    def largestRectangleArea(self, heights: list[int]) -> int:
        length = len(heights)
        if length == 0:
            return 0
        if length == 1:
            return heights[0]
        heights = [0] + heights + [0]
        length += 2
        area = 0
        stack = list()
        for i in range(length):
            while len(stack) != 0 and heights[stack[-1]] > heights[i]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                area = max(area, width * height)
            stack.append(i)
        return area
